import java.util.*;

/**
 * @author lzhphantom
 * @description
 * @create 2020年6月10日 17点24分
 */
public class Solution {
    /**
     * @param l1: the first list
     * @param l2: the second list
     * @return the product list of l1 and l2
     * @description 给出两个链表形式表示的数字, 写一个函数得到这两个链表相乘乘积。
     */
    public long multiplyLists(ListNode l1, ListNode l2) {
        // write your code here
        return getNumber(l1, 0) * getNumber(l2, 0);
    }

    private long getNumber(ListNode node, long initNumber) {
        long result = initNumber;
        if (node != null) {
            result = result * 10 + node.val;
        }
        if (node.next != null) {
            result = getNumber(node.next, result);
        }
        return result;
    }

    /**
     * @param str: a string
     * @return return a list of strings
     */
    public String toLowerCase(String str) {
        String result = "";
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch >= 65 && ch <= 91) {
                ch += 32;
            }

            result += ch;
        }
        return result;
    }

    /**
     * @param nums: A list of integers
     * @return An integer denotes the middle number of the array
     * @description 给定一个未排序的整数数组，找到其中位数。
     * <p>
     * 中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
     */
    public int median(int[] nums) {
        // write your code here
        Arrays.sort(nums);
        int mid = nums.length % 2 == 0 ? nums.length / 2 + 1 : nums.length / 2;
        return nums[mid];
    }

    /**
     * 设计一种方法，通过给重复字符计数来进行基本的字符串压缩。
     * <p>
     * 例如，字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数，则返回原始的字符串。
     * <p>
     * 可以假设字符串仅包括 a-z 的字母。
     *
     * @param originalString: a string
     * @return a compressed string
     */
    public String compress(String originalString) {
        // write your code here
        int num = 0;
        String result = "";
        char currentCh = '0';
        for (int i = 0; i < originalString.length(); i++) {
            if (i == 0) {
                currentCh = originalString.charAt(i);
                num++;
                continue;
            }
            if (originalString.charAt(i) == currentCh) {
                num++;
            } else {
                result += String.valueOf(currentCh) + num;
                currentCh = originalString.charAt(i);
                num = 1;
            }
        }
        result += String.valueOf(currentCh) + num;
        return result.length() < originalString.length() ? result : originalString;
    }

    /**
     * @param source:
     * @param target:
     * @return return the index
     */
    public int strStr(String source, String target) {
        // Write your code here
        if ("".equals(target) || source.equals(target)) {
            return 0;
        }
        int result = -1;
        if (target.length() > source.length()) {
            return result;
        }
        Map<Integer, String> strMap = new HashMap<>(0);
        for (int i = 0; i < source.length(); i++) {
            if (i + target.length() > source.length()) {
                break;
            } else {
                strMap.put(i, source.substring(i, i + target.length()));
            }
        }
        if (strMap.containsValue(target)) {
            for (int key : strMap.keySet()) {
                if (strMap.get(key).equals(target)) {
                    result = key;
                    break;
                }
            }
        }

        return result;
    }

    /**
     * @param dictionary: an array of strings
     * @return an arraylist of strings
     * @description 给一个词典，找出其中所有最长的单词。
     */
    public List<String> longestWords(String[] dictionary) {
        // write your code here
        int theMaxLength = 0;
        List<String> strList = new ArrayList<>();
        for (int i = 0; i < dictionary.length; i++) {
            if (i == 0) {
                strList.add(dictionary[i]);
                theMaxLength = dictionary[i].length();
                continue;
            }
            if (dictionary[i].length() > theMaxLength) {
                theMaxLength = dictionary[i].length();
                strList.clear();
                strList.add(dictionary[i]);
            } else if (dictionary[i].length() == theMaxLength) {
                strList.add(dictionary[i]);
            }
        }
        return strList;
    }

    /**
     * @param arr: An integer array
     * @return An integer
     * @description 落单的数
     * 给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
     */
    public int singleNumber(int[] arr) {
        // write your code here
        Arrays.sort(arr);
        if (arr.length == 1) {
            return arr[0];
        }
        if (arr.length == 0) {
            return 0;
        }
        int count = 0;
        int curNum = 0;
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                curNum = arr[i];
                result = curNum;
                count++;
                continue;
            }
            if (arr[i] == curNum) {
                count++;
            } else if (count == 2) {
                curNum = arr[i];
                result = curNum;
                count = 1;
            } else {
                break;
            }

        }
        return result;
    }

    /**
     * @param nums: a list of integers
     * @return A integer indicate the sum of minimum subarray
     * @description 最小子数组
     * 给定一个整数数组，找到一个具有最小和的连续子数组。返回其最小和。
     */
    public int minSubArray(List<Integer> nums) {
        // write your code here
        if (nums.isEmpty()) {
            return 0;
        }
        TreeSet<Integer> minArr = new TreeSet<>();
        for (int i = 0; i < nums.size(); i++) {
            int total = nums.get(i);
            minArr.add(total);
            for (int j = i + 1; j < nums.size(); j++) {
                total += nums.get(j);
                minArr.add(total);
            }
        }
        return minArr.iterator().next();
    }

    /**
     * 给定一个列表，该列表中的每个元素要么是个列表，要么是整数。将其变成一个只包含整数的简单列表。
     *
     * @param nestedList nestedList a list of NestedInteger
     * @return a list of integer
     */
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> results = new ArrayList<>();
        for (NestedInteger nestedInteger : nestedList) {
            if (nestedInteger.isInteger()) {
                results.add(nestedInteger.getInteger());
            } else {
                results.addAll(flatten(nestedInteger.getList()));
            }
        }

        return results;
    }

    /**
     * @param nums: a list of integers
     * @return find a  majority number
     * @description 给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。
     */
    public int majorityNumber(List<Integer> nums) {
        // write your code here
        Map<Integer, Integer> count = new HashMap<>(0);
        for (Integer num : nums) {
            if (count.containsKey(num)) {
                count.put(num, count.get(num) + 1);
            } else {
                count.put(num, 1);
            }
        }
        int result = -1;
        for (Integer i : count.keySet()) {
            if (count.get(i) > nums.size() / 2) {
                result = i;
            }
        }
        return result;
    }

    /**
     * @param nums: Given an integers array A
     * @return A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     * @description 给定一个整数数组A。
     * 定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。
     */
    public List<Long> productExcludeItself(List<Integer> nums) {
        // write your code here
        List<Long> result = new ArrayList<>(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            result.add(1L);
        }
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < result.size(); j++) {
                if (i == j) {
                    continue;
                } else if (i == 0 && j != 0) {
                    result.set(j, (long) nums.get(i));
                } else {
                    result.set(j, result.get(j) * nums.get(i));
                }
            }
        }
        return result;
    }

    /**
     * 给定一个字符串，逐个翻转字符串中的每个单词。
     *
     * @param s: A string
     * @return A string
     */
    public String reverseWords(String s) {
        // write your code here
        String[] arr = s.split(" ");
        if (arr.length == 0) {
            return "";
        }
        String result = "";
        for (int i = arr.length - 1; i > 0; i--) {
            if (!"".equals(arr[i])) {
                result += arr[i] + " ";
            }
        }
        result += arr[0];
        return result;
    }

    /**
     * 给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
     *
     * @param sorted: an integer sorted array
     * @param target: an integer to be inserted
     * @return An integer
     */
    public int searchInsert(int[] sorted, int target) {
        int result = 0;
        if (sorted.length == 0) {
            return result;
        }
        for (int i = 0; i < sorted.length; i++) {
            if (sorted[i] >= target) {
                return i;
            }
        }
        if (result == 0) {
            result = sorted.length;
        }
        return result;
    }

    /**
     * @param arr: sorted integer array A which has m elements, but size of A is m+n
     * @param m:   An integer
     * @param brr: sorted integer array B which has n elements
     * @param n:   An integer
     * @return nothing
     */
    public void mergeSortedArray(int[] arr, int m, int[] brr, int n) {
        // write your code here
        int i = m - 1, j = n - 1, index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (arr[i] > brr[j]) {
                arr[index--] = arr[i--];
            } else {
                arr[index--] = brr[j--];
            }
        }
        while (i >= 0) {
            arr[index--] = arr[i--];
        }
        while (j >= 0) {
            arr[index--] = brr[j--];
        }
    }

    /**
     * @param n
     * @return int[][]
     * @description
     * @method generateMatrix
     * @author lzhphantom
     * @date 14:53 2020/7/15
     */
    public int[][] generateMatrix(int n) {
        if (n < 0) {
            return null;
        }

        int[][] result = new int[n][n];

        int xStart = 0;
        int yStart = 0;
        int num = 1;
        boolean addFlag = true;

        while (n > 0) {
            if (n == 1) {
                result[yStart][xStart] = num++;
                break;
            }

            for (int i = 0; i < n - 1; i++) {
                if (num == 9) {
                    addFlag = false;
                } else if (num == 1) {
                    addFlag = true;
                }
                result[yStart][xStart + i] = addFlag ? num++ : num--;
            }

            for (int i = 0; i < n - 1; i++) {
                if (num == 9) {
                    addFlag = false;
                } else if (num == 1) {
                    addFlag = true;
                }
                result[yStart + i][xStart + n - 1] = addFlag ? num++ : num--;
            }

            for (int i = 0; i < n - 1; i++) {
                if (num == 9) {
                    addFlag = false;
                } else if (num == 1) {
                    addFlag = true;
                }
                result[yStart + n - 1][xStart + n - 1 - i] = addFlag ? num++ : num--;
            }

            for (int i = 0; i < n - 1; i++) {
                if (num == 9) {
                    addFlag = false;
                } else if (num == 1) {
                    addFlag = true;
                }
                result[yStart + n - 1 - i][xStart] = addFlag ? num++ : num--;
            }

            xStart++;
            yStart++;
            n = n - 2;
        }

        return result;
    }

    /**
     * 是否是2的幂次方
     *
     * @param n: an integer
     * @return if n is a power of two
     */
    public boolean isPowerOfTwo(int n) {
        // Write your code here
        if (n <= 0) {
            return false;
        }
        return (n & (n - 1)) == 0;
    }

}
